package com.kiwi.nixu;

import com.kiwi.nixu.common.LNode;

import java.util.LinkedHashMap;

/**
 * @Author: zqb
 * @Description:如何找出单链表中的倒数第k个元素 m1:快慢指针法
 * 引申：如何将单链表向右旋转k个位置
 * @Date: Created in 17:46 2020/1/22
 * @Create By:
 */
public class FindKNumOfLinkedList {

    public static LNode constructList() {
        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        return head;
    }

    public static void printList(LNode head) {
        for (LNode cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
    }

    /**
     * 思路：快慢指针
     * 由于单链表只能从头到尾依次访问链表的各个结点，因此如果要找单链表的倒数第k 个元素，
     * 也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，
     * 让其中一个指针比另外一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为null时，
     * 另一个指针所指的位置就是所要找的位置
     *
     * @param head
     * @return
     */
    public static LNode findLastK(LNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        //快慢指针
        LNode fast, slow;
        slow = fast = head.next;
        int i;

        for (i = 0; i < k && fast != null; i++) {
            fast = fast.next;
        }
        //判断k是否已超出链表的长度
        if (i < k) {
            return null;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        LNode head = constructList();
        LNode result = null;
        System.out.print("链表：");
        printList(head);
        result = findLastK(head, 3);
        if (result != null) {
            System.out.println("\n 链表倒数第三个元素为：" + result.data);
        }

    }
}
